﻿//#define _CRT_SECURE_NO_WARNINGS  1
////一定要动手，例子不管多么简单，建议至少自己手敲一遍看看是否理解了里头的细枝末节。
////一定要学会思考，思考为什么要这样，而不是那样。还要举一反三地思考
//#include<iostream>
//#include<assert.h>
//#include<string>
//using namespace std;
////选择排序
////void InsertSort(int* a, int n)
////{
////	int end = n;
////	int begin = 1;
////	for (int end = n - 1; end > 0; end--)
////	{
////		for (int begin = 1; begin <= end; begin++)
////		{
////			if (a[begin - 1] > a[begin])
////			{
////				swap(a[begin - 1], a[begin]);
////			}
////		}
////	}
////}
////希尔排序
//void ShellSort(int* a, int n)
//{
//	/*int gap = n / 2;
//	while (gap >=1)
//	{
//		for (int begin = 0; begin <= n-gap; begin++)
//		{
//			for (int end = begin; end <= n - gap-1; end += gap)
//			{
//				if (a[end] > a[end + gap])
//				{
//					swap(a[end], a[end + gap]);
//				}
//			}
//		}
//		gap = gap / 2;
//	}*/
//	int gap = n;
//	while (gap > 0)
//	{
//		gap /= 2;
//		//单趟排序
//		for (int i = 0; i < n - gap; i++)
//		{
//			int end = i;
//			int x = a[end + gap];
//			while (end >= 0)
//			{
//				if (a[end] > x)
//				{
//					a[end + gap] = a[end];
//					end -= gap;
//				}
//				else {
//					break;
//				}
//			}
//			a[end + gap] = x;
//		}
//	}
//}
//void SelectSort(int* a, int n)
//{
//	int left = 0;
//	int right = n - 1;
//	while (left < right)
//	{
//		int max = right;
//		int min = left;
//		int begin = left;
//		int end = right;
//		while (begin < end )
//		{
//			if (a[begin] >= a[max]){
//				max = begin;
//			}
//			if (a[begin] <= a[min]){
//				min = begin;
//			}
//			begin++;
//		}
//		swap(a[min], a[left]);
//		if (max == left){
//			max = min;
//		}
//		swap(a[max], a[right]);
//		left++;
//		right--;
//	}
//}
//void AdjustUp(int* a, int child)
//{
//	assert(a);
//	int parent = (child - 1) / 2;
//	while (child > 0)
//	{
//		if (a[parent] <= a[child])
//		{
//			swap(a[parent], a[child]);
//			child = parent;
//			parent = (child-1) / 2;
//		}
//		else {
//			break;
//		}
//	}
//}
//void AdjustDown(int* a, int parent)
//{
//	assert(a);
//	int child ;
//	//找到大的孩子
//	while (parent >= 0)
//	{
//		child = parent * 2 + 1;
//		if (a[child] < a[child + 1])
//		{
//			child++;
//		}
//		if (a[child] > a[parent])
//		{
//			swap(a[child], a[parent]);
//		}
//		parent--;
//	}
//}
////堆排序
//void HeapSort(int* a, int n)
//{
//	//建堆（向下调整建堆）时间复杂度：
//	int child = n - 1;
//	int parent = (child - 1) / 2;
//	for (int i = parent; i >= 1; i--)
//	{
//		AdjustDown(a, i);
//	}
//
//
//
//	//建堆（向上调整建堆）时间复杂度；
//	/*for (int i = 0; i < n; i++)
//	{
//		AdjustUp(a, i);
//	}*/
//
//}
//void InsertSort(int* a, int n)
//{
//	int x;
//	for (int i = 0; i < n - 1; i++)
//	{
//		int end = i;
//		x = a[end + 1];
//		while (end >= 0)
//		{
//			if (a[end] > x)
//			{
//				a[end + 1] = a[end];
//			}
//			else
//			{
//				break;
//			}
//			end--;
//		}
//		a[end + 1] = x;
//	}
//}
//void test()
//{
//	int a[] = { 7,3,9,6,2,8,4,5 };
//
//	/*插入排序*/
//	//InsertSort(a, sizeof(a)/sizeof(a[0]));
//
//	/*希尔排序*/
//	/*ShellSort(a, sizeof(a) / sizeof(a[0]));*/
//
//	//选择排序
//	/*SelectSort(a, sizeof(a) / sizeof(a[0]));*/
//
//	//堆排序
//	HeapSort(a,sizeof(a)/sizeof(a[0]));
//	/*for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
//	{
//		
//	}
//	cout << endl;*/
//	//插入排序
//	//InsertSort(a, sizeof(a) / sizeof(a[0]));
//	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
//	{
//		cout << a[i] <<" ";
//	}
//	cout << endl;
//}
//int main()
//{
//	test();
//	return 0;
//}